package alo.p4.work;

import java.util.Stack;

//计算跨度
public class FindingSpans {
    int[] findingSpans(int[] inputArray){
        int[] spans=new int[inputArray.length];
        for (int i = 0; i < inputArray.length; i++) {
            int span=1;
            int j=i-1;
            while (j>0&&inputArray[j]<inputArray[j+1]){
                span++;
                j--;
            }
            spans[i]=span;
        }
        return spans;

    }
    //使用栈
    //判断前面有几个比自己小
    int[] findingSpans2(int[] inputArray){
        int[] spans=new int[inputArray.length];
        Stack stack=new Stack();
        int p=0;

        for (int i = 0; i < inputArray.length; i++) {
            int j=i;
            while (!stack.isEmpty()&&inputArray[j--]>inputArray[(int) stack.peek()]){
                stack.pop();
            }
            if (stack.isEmpty()) p=-1;
            else p= (int) stack.pop();
            spans[i]=i-p;
            stack.push(i);
        }
        return spans;

    }
}
